The transmission rates for local area networks (LANs) that use twisted pair conductors have progressively increased from 10 Megabits-per-second (Mbps) to 1 Gigabit-per-second (Gbps). The Gigabit Ethernet 1000 Base-T standard, for example, operates at a clock rate of 125 MHz and uses category 5 cabling with four copper pairs to transmit 1 Gbps. Trellis-coded modulation (TCM) is employed by the transmitter, in a known manner, to achieve coding gain. The signals arriving at the receiver are typically corrupted by intersymbol interference (ISI), crosstalk, echo, and noise. A major challenge for 1000 Base-T receivers is to jointly equalize the channel and decode the corrupted trellis-coded signals at the demanded clock rate of 125 MHz, as the algorithms for joint equalization and decoding incorporate non-linear feedback loops that cannot be pipelined.
Data detection is often performed using maximum likelihood sequence estimation (MLSE), to produce the output symbols or bits. A maximum likelihood sequence estimator considers all possible sequences and determines which sequence was actually transmitted, in a known manner. The maximum likelihood sequence estimator is the optimum decoder and applies the well-known Viterbi algorithm to perform joint equalization and decoding. For a more detailed discussion of a Viterbi implementation of a maximum likelihood sequence estimator, see Gerhard Fettweis and Heinrich Meyr, “High-Speed Parallel Viterbi Decoding Algorithm and VLSI-Architecture,” IEEE Communication Magazine (May 1991), incorporated by reference herein.
In order to reduce the hardware complexity for the maximum likelihood sequence estimator that applies the Viterbi algorithm, a number of sub-optimal approaches, such as “reduced state sequence estimation (RSSE)” algorithms, have been proposed or suggested. For a discussion of reduced state sequence estimation techniques, as well as the special cases of decision-feedback sequence estimation (DFSE) and parallel decision-feedback equalization (PDFE) techniques, see, for example, P. R. Chevillat and E. Eleftheriou, “Decoding of Trellis-Encoded Signals in the Presence of Intersymbol Interference and Noise”, IEEE Trans. Commun., vol. 37, 669–76, (July 1989), M. V. Eyuboglu and S. U. H. Qureshi, “Reduced-State Sequence Estimation For Coded Modulation On Intersymbol Interference Channels”, IEEE JSAC, vol. 7, 989–95 (August 1989), or A. Duel-Hallen and C. Heegard, “Delayed decision-feedback sequence estimation,” IEEE Trans. Commun., vol. 37, pp. 428–436, May 1989, each incorporated by reference herein. For a discussion of the M algorithm, see, for example, E. F. Haratsch, “High-Speed VLSI Implementation of Reduced Complexity Sequence Estimation Algorithms With Application to Gigabit Ethernet 1000 Base-T,” Int'l Symposium on VLSI Technology, Systems, and Applications, Taipei (June 1999), incorporated by reference herein.
Generally, reduced state sequence estimation techniques reduce the complexity of the maximum likelihood sequence estimators by merging several states. The reduced state sequence estimation technique incorporates non-linear feedback loops that cannot be pipelined. The critical path associated with these feedback loops is the limiting factor for high-speed implementations.
U.S. patent application Ser. No. 09/326,785, filed Jun. 4, 1999 and entitled “Method and Apparatus for Reducing the Computational Complexity and Relaxing the Critical Path of Reduced State Sequence Estimation Techniques,” incorporated by reference herein, discloses a reduced state sequence estimation algorithm that reduces the hardware complexity of reduced state sequence estimation techniques for a given number of states and also relaxes the critical path problem. While the disclosed reduced state sequence estimation algorithm exhibits significantly improved processing time, additional processing gains are needed for many high-speed applications. A need therefore exists for a reduced state sequence estimation algorithm with improved processing time. Yet another need exists for a reduced state sequence estimation algorithm that is better suited for a high-speed implementation using very large scale integration (VLSI) techniques.